public class Leet403 {
    public static void main(String[] args) {
        Leet403 l = new Leet403();
        System.out.println(l.canCross(new int[]{0,1,2,3,4,8,9,11}));
    }
    static boolean flag;
    static int[][] dp;
    public boolean canCross(int[] stones) {
        flag = false;
        dp = new int[stones.length][stones.length];
        dfs(stones,0,0);
        return flag;
    }
    void dfs(int[] stone,int at,int power){
        if (dp[at][power] == 1)
            return;
        else dp[at][power] = 1;
        if (at==stone.length-1){
            flag = true;
            return;
        }
        if (!flag)
        for (int i = at+1; i < stone.length; i++)
            if (stone[i]-stone[at]<=power+1&&stone[i]-stone[at]>=power-1)
                dfs(stone, i, stone[i]-stone[at]);
            else if (stone[i]-stone[at]>power+1)
                break;
    }
}
